1. Field of the Invention
The present invention relates to a system and method for evaluating the performance of a potential route before it is actually established.
2. Description of the Related Art
Wireless communication networks, such as mobile wireless telephone networks, have become increasingly prevalent over the past decade. These wireless communications networks are commonly referred to as “cellular networks”, because the network infrastructure is arranged to divide the service area into a plurality of regions called “cells”. A terrestrial cellular network includes a plurality of interconnected base stations, or base nodes, that are distributed geographically at designated locations throughout the service area. Each base node includes one or more transceivers that are capable of transmitting and receiving electromagnetic signals, such as radio frequency (RF) communications signals, to and from mobile user nodes, such as wireless telephones, located within the coverage area. The communications signals include, for example, voice data that has been modulated according to a desired modulation technique and transmitted as data packets. As can be appreciated by one skilled in the art, network nodes transmit and receive data packet communications in a multiplexed format, such as time-division multiple access (TDMA) format, code-division multiple access (CDMA) format, or frequency-division multiple access (FDMA) format, which enables a single transceiver at a first node to communicate simultaneously with several other nodes in its coverage area.
In recent years, a type of mobile communications network known as an “ad-hoc” network has been developed. In this type of network, each mobile node is capable of operating as a base station or router for the other mobile nodes, thus eliminating the need for a fixed infrastructure of base stations.
More sophisticated ad-hoc networks are also being developed which, in addition to enabling mobile nodes to communicate with each other as in a conventional ad-hoc network, further enable the mobile nodes to access a fixed network and thus communicate with other mobile nodes, such as those on the public switched telephone network (PSTN), and on other networks such as the Internet. Details of these advanced types of ad-hoc networks are described in U.S. Pat. No. 7,072,650 entitled “Ad Hoc Peer-to-Peer Mobile Radio Access System Interfaced to the PSTN and Cellular Networks”, issued on Jul. 4, 2006, in U.S. Pat. No. 6,807,165 “Time Division Protocol for an Ad-Hoc, Peer-to-Peer Radio Network Having Coordinating Channel Access to Shared Parallel Data Channels with Separate Reservation Channel”, issued on Oct. 19, 2004, and in U.S. Pat. No. 6,873,839 entitled “Prioritized-Routing for an Ad-Hoc, Peer-to-Peer, Mobile Radio Access System”, issued on Mar. 29, 2005, the entire content of each being incorporated herein by reference.
A node in a wireless network usually sends data to another node by establishing a route to that other node. Sometimes a third node will act as a proxy. In order to maximize the performance of the network (i.e. maximize the amount of traffic that each node is capable of carrying across the network), routes are typically established by minimizing or maximizing a cost function; the “route metric”. This metric can be based on a variety of parameters, such as the number of hops, the signal strength, the signal-to-noise ratio (SNR), the congestion, the battery power, the packet completion rate, the data rate, the queue size, the packet size, the type of traffic or other metrics. However, some of the most valuable metrics (such as the completion rate and the data rate) are impossible to establish with precision unless some traffic is being sent on each link. Since generating traffic on each link is a waste of bandwidth (and therefore a hindrance to maximizing performance), there is a need for a more suitable way of determining the route metric without generating an unnecessarily large amount of traffic.
Routing algorithms circumvent this problem by making a rough (and therefore, wholly inaccurate) estimation based on statistics collected passively, for example, by listening to beacons or control traffic. The statistics that are collected passively present a series of problems. First of all, these statistics may become stale if the nodes in the wireless network are highly mobile. Secondly, statistics that are collected passively are very imprecise compared to statistics that are collected when active traffic is being sent between two nodes of a wireless network. For these reasons, the route metrics that are derived from statistics collected passively may induce the routing algorithm to select an unusable route. There is therefore a need for a protocol that makes more informed decisions before the establishment of a route. Currently known methods to search for routes in a wireless network include the establishment of a new route based on a priori information. One example of this method is described in U.S. Patent Application No. 2004/0143842 (“System and method for achieving continuous connectivity to an access point or gateway in a wireless network following an on-demand routing protocol, and to perform smooth handoff of mobile terminals between fixed terminals in the network”).
In the method described in the above referenced application, if a node receives a hello message suggesting a better route to the access point, this node will immediately switch routes. After the establishment of the new route, traffic may be sent along the route. It is possible that the route metric that is determined as the route is being used to send traffic ends up being considerably worse than the route metric that was determined using the statistics collected passively. The update route metric could be so much worse as to trigger the re-establishment of the previously abandoned route. It is therefore desirable to have a system that ensures that the new offered route is indeed better than the previously used one before a new route is established.
Other methods to search for routes in a wireless network involve the maintenance of multiple routes. Some on demand routing protocols like Dynamic Source Routing (DSR) and Ad-hoc On-demand Multipath Distance Vector (AOMDV) routing maintain multiple routes to a destination. A node can either use multiple routes simultaneously or can just use one route and switch immediately to the other if the current route breaks. The simultaneous use of routes can cause problems due to the out-of-order delivery of packets and hence the other use of multiple routes is preferred. Although alternate routes are valid routes at the time of creation, as time goes by they may become stale or have worse metrics. It would be desirable to have a method that prevents alternate routes from becoming stale.
Another method to search for routes in a wireless network involves the estimation of the route metric based on the transmission of data packets. This method requires the transmission of periodic data packets or beacons and then estimating the quality based on the receive statistics. This can provide an accurate estimation but only after incurring high overhead. It would be desirable to have a method that limits the extra amount of overhead.
Other algorithms have been devised to improve network performance by performing actions akin to scouting. In one such algorithm (“PLANet: an active internetwork”), presented by Michael Hicks et al., the authors write “However, we will periodically intersperse scout packets that will explore the network searching for a better route and directing the flow of the transport packets. Each scout packet fits within a 1500 byte Ethernet frame, yet carries out some non-trivial computations. In particular, at each hop, the scout packet will send a copy of itself on each of the router's outgoing interfaces, thus fanning out over the network.” Because of the dissemination of the scout packet all across the network, the use of PLANet is restricted to wired networks. There is therefore a need for a method to scout for routes in a wireless network while limiting the amount of signaling overhead.
Another algorithm that uses a method akin to scouting is presented in U.S. Pat. No. 6,798,765 (“Method for forwarding in multihop networks”), issued on Sep. 28, 2004. The application describes a “method for forwarding information in a multihop network comprising a plurality of nodes, comprising the steps of: designating a node in the network as an originating node; transmitting a probe message from the originating node in the network to a plurality of other nodes in the network in a general direction in which the information is to be forwarded”. However, each probe is limited to an individual hop. There is therefore a need for a method to scout for routes across a plurality of hops in a wireless network.